1. Field of the Invention
The present invention relates to the field of digital data processing. More specifically, the present invention relates to the design of high speed parallel adder in a digital data processor.
2. Background Information
Addition is one of the essential tasks repeatedly performed by a digital data processor. As a result, the adder is an essential part of a digital data processor. In addition to being used to perform addition, often times, the adder is also an integral part of the multiplier, playing an important role in the performance of multiplication. Thus, much effort has been expanded to try to maximize the speed of adders, and any further improvement on the speed of adders is desirable.
Numerous schemes for performing high speed addition had been proposed. One such scheme was proposed by Dozza et al. during the 1996 IEEE International Symposium on Circuits and Systems, held in Atlanta, Ga., May 12-15, 1996. The presentation was entitled "A 3.5 ns, 64 bit, carry-lookahead adder". Briefly, Dozza's proposal extends the work of Brent and Kung, which opened the way to a class of carry-lookahead adders based on a binary tree structure. Under Dozza's approach, a compact array of cells, each implementing what's known as the "O" operator, are interconnected in accordance with a particular binary tree structure. The tree structure is shown in FIG. 1b of an article subsequently published as part of the proceeding of the conference. The sum and the carry out bits are computed in accordance with the equations: EQU s.sub.i =p.sub.i XOR c.sub.i-1, and c.sub.i =g.sub.i +p.sub.i c.sub.i-1,,
where g.sub.i =a.sub.i b.sub.i and p.sub.i =a.sub.i XOR b.sub.i PA1 a.sub.i and b.sub.i are inputs to the adders, and PA1 g.sub.i and p.sub.i are generate and propagate bits.
The generate and propagate bits are recursively calculated with EQU g.sub.ik =g.sub.j+1,k +p.sub.j+1,k g.sub.ij and p.sub.ik =p.sub.ij p.sub.j+1,k
for i&lt;j and j+1&lt;k. Dozza's approach was able to reduce the length of the critical path to log.sub.2 n logical levels (as opposed to the requirement of 2log.sub.2 (n-1) logical levels under Brent and Kung), while keeping the fan-out down to 2 for each cell. Brent and Kung's work are described in R. P. Brent and H. T. Kung, "A Regular Layout for Parallel Adders", IEEE Trans. Comput., vol. C-31, no. 3, pp. 260-264, March 1982."
The present invention further improves on Dozza's approach.